package backtrack_or_fs.bfs_dfs;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.TreeSet;



class 岛屿的最大面积_695_重做版{ // 对每个点  进行dfs  累计面积
            final int[][] moves = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
            public int maxAreaOfIsland(int[][] grid) {
                int row = grid.length, 
                col = grid[0].length,
                max = 0;
                boolean[][] visited = new boolean[row][col];
                for(int i = 0; i< row; i++) {
                    for(int j = 0; j < col; j++) {
                        if(visited[i][j]) continue;
                        if(grid[i][j] == 0){
                            visited[i][j] = true;
                            continue;
                        } 
                        max = Math.max(max, dfs(grid, i, j, visited));
                    }
                }
                return max;
            }

            private int dfs(int[][] grid, int i ,int j, boolean[][] visited) {
                int area = 0;
                if(grid[i][j] == 0) {
                    visited[i][j] = true;
                    return area;
                }
                visited[i][j] = true;
                area += 1;
                for(int k = 0; k< 4; k++){
                    int ni = i + moves[k][0];
                    int nj = j + moves[k][1];
                    if(ni >=0 && ni < grid.length && nj >=0 && nj < grid[0].length && !visited[ni][nj]) {
                       area += dfs(grid, ni, nj, visited); 
                    }
                } 
                return area;
            }
        }
/**
 * 给定一个包含了一些 0 和 1 的非空二维数组 grid 。
 * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
 * 你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 * 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
 * 示例 1:
 *
 * [[0,0,1,0,0,0,0,1,0,0,0,0,0],
 *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
 *  [0,1,1,0,1,0,0,0,0,0,0,0,0],
 *  [0,1,0,0,1,1,0,0,1,0,1,0,0],
 *  [0,1,0,0,1,1,0,0,1,1,1,0,0],
 *  [0,0,0,0,0,0,0,0,0,0,1,0,0],
 *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
 *  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
 *
 * 示例 2:
 *
 * [[0,0,0,0,0,0,0,0]]
 * 对于上面这个给定的矩阵, 返回 0。
 *
 *
 * 网格 + 搜索问题的典型
 */
public class 岛屿最大面积_695 {
    // 每个单元格都是树的根  可向上下左右四个方向搜索， 可以看成是4叉树
    // 坐标偏移量 可向上下左右四个方向进行搜索
    int[] rowShift = {-1,1,0,0};
    int[] columnShift = {0,0,-1,1};
    public int maxAreaOfIsland(int[][] grid) {
        // 遍历每个单元格  针对每个单元格进行深度搜索
        int maxArea = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }


    private int dfs(int[][] grid, int cur_i, int cur_j) {
        // 数组下标越界
        if(cur_i <= 0 || cur_i >= grid.length ||cur_j <= 0 || cur_j >= grid[0].length ){
            return 0;
        }
        // 当前点不是小岛的陆地
        if(grid[cur_i][cur_j] == 0) {
            return 0;
        }
        // 当前点面积记为1
        int count = 1 ;
        // 避免反向搜回来又加了本节点面积
        grid[cur_i][cur_j] = 0;
        for(int i = 0; i < rowShift.length; i++) {
            count += dfs(grid, cur_i + rowShift[i], cur_j + columnShift[i]);
        }
        return count;
    }

}
